﻿#include<iostream>
using namespace std;

//【题目】力扣222.完全二叉树的节点个数
//【难度】简单
//【提交】https://leetcode.cn/problems/count-complete-tree-nodes/submissions/666015374/
//【标签】位运算；树；二分查找；二叉树
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution 
{
public:
    // 求二叉树的深度
    int countLevels(TreeNode* root) 
    {
        int levels = 0;
        while (root) 
        {
            root = root->left; levels += 1;
        }
        return levels;
    }
    bool is_exist(TreeNode* root, int index, int depth) 
    {
        TreeNode* node = root;
        while (depth) 
        {
            int mid = ((1 << depth) >> 1);
            if (index > mid) 
            {
                index -= mid;
                node = node->right;
            }
            else
            {
                node = node->left;
            }
            depth -= 1;
        }
        return node != nullptr;
    }

    int countNodes(TreeNode* root) 
    {
        if (root == nullptr) return 0;
        int depth = countLevels(root);
        int depth_prev = depth - 1;

        int start = 1, end = (1 << depth_prev), mid = 0;
        while (start <= end) 
        {
            mid = start + (end - start) / 2;
            if (is_exist(root, mid, depth_prev)) start = mid + 1;
            else end = mid - 1;
        }
        int ret = (1 << depth_prev) - 1 + start - 1;
        return ret;
    }
};

/*
学习总结：
利用完全二叉树性质：完全二叉树的底层节点从左到右连续排列，且除底层外前h−1层是满节点（共2^(h−1个0节点）。
问题转化为计算底层节点的数量。

二分查找定位底层节点：
先计算树的高度h（通过左子树深度），底层最多有2^(h−1)个节点。
对底层节点编号（1 到 2^(h-1)），通过二分法确定最后一个存在的节点编号。

关键函数 is_exist 利用二进制位判断路径（0 向左，1 向右），检查某编号节点是否存在。
*/